package offerbook;

/**
 * 给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
 * 不得使用库函数，并且不应考虑大数问题。
 * 求一个数的N次方，要考虑一下几点。
 * 1 如果底数是0
 * 1.1 指数小于等于0均非法
 * 1.2 指数大于0均返回0
 * <p>
 * 2 如果底数非0
 * 1.1 指数大于0
 * 1.2 指数小于0
 *
 * @date 2020/3/8 18:31
 */
public class Code11_PowerOfNum {
    public static double powOfNum1(double base, int exp) {
        if (equalsZero(base, 0.d)) {
            if (exp <= 0) throw new RuntimeException("illegal");
            else return 0; // 0^ positive
        }
        int tempExp = exp > 0 ? exp : -exp;
//        double res = getRes1(base,tempExp);
        //TODO BUG，exp是INT_MIN_VALUE， 0 -INT_MIN_VALUE = INT_MIN_VALUE
        //TODO 传入到getRes中也是INT_MIN_VALUE
        double res = getRes2(base, tempExp);
        return exp > 0 ? res : 1 / res;
    }

    /**
     * 利用公式 a^n = a^(n/2) * a^(n/2) ,n为偶数。
     * a^n = a^(n-1/2) * a^(n-1/2)*a,n为奇数，加速过程。
     * log(exp)的时间复杂度，空间复杂度是递归栈log(n)
     */
    private static double getRes2(double base, int exp) {
        if (exp == 0) return 1;
        if (exp == 1) return base;
        //如果是偶数，那么8-4-2-1
        //如果是奇数，那么9-4-2-1,最后还要乘以一个base
        //TODO BUG,exp是INT_MIN_VALUE时， exp >> 1会一直是负数，递归爆了
        //TODO 可以用exp >>> 1或者 exp / 2
        double temp = getRes2(base, exp >>> 1);
        temp *= temp;
        if ((exp & 1) != 0) temp *= base;
        return temp;
    }

    /**
     * 时间复杂度O(exp)
     */
    private static double getRes1(double base, int exp) {
        if (exp == 0) return 1;
        if (exp == 1) return base;
        double res = 1.0d;
        for (int i = 0; i < exp; i++) {
            res *= base;
        }
        return res;
    }

    private static boolean equalsZero(double e1, double e2) {
        double error = 1e-6;
        if (Math.abs(e1 - e2) <= error) return true;
        return false;
    }
}
